/*
 * @lc app=leetcode.cn id=74 lang=cpp
 *
 * [74] 搜索二维矩阵
 */

// @lc code=start
class Solution
{
 public:
  /* 二分法：
  /* 尝试写错了
  /* 主要是可以把matrix展开成一个区间，matrix的定位公式，这块我没想到
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
      if(matrix.empty()) return false;
      int rows = matrix.size(), cols=matrix[0].size();
      int l =0, r = rows-1;
      while(l<r)
      {
          int mid = 1+r+l>>1;
          if(matrix[mid][cols-1]<=target)  l=mid;
          else r=mid-1;
      }
      if(matrix[l][cols-1]<target) return false;
      int exist_row = l;

      l=0,r=cols-1;
      while(l<r)
      {
          int mid = 1+r+l>>1;
          if(matrix[exist_row][mid]<=target) l=mid;
          else r=mid-1;
      }
      if(matrix[l][0]>target) return false;
      return true;
  }
  */

  bool searchMatrix(vector<vector<int>>& matrix, int target)
  {
    if (matrix.empty() || matrix[0].empty()) return false;

    int n = matrix.size(), m = matrix[0].size();
    int l = 0, r = n * m - 1;
    while (l < r)
    {
      int mid = l + r >> 1;
      if (matrix[mid / m][mid % m] >= target)
        r = mid;
      else
        l = mid + 1;
    }

    if (matrix[r / m][r % m] != target) return false;
    return true;
  }

  bool searchMatrix(vector<vector<int>>& matrix, int target)
  {
    if (matrix.empty() || matrix[0].empty()) return false;

    //开始查找
    int i = 0, j = matrix[0].size() - 1;  //从右上角开始
    while (i < matrix.size() && j >= 0)
    {
      if (matrix[i][j] == target) return true;  //最后的逻辑

      if (matrix[i][j] > target)
        j--;  //右上角都大，这一列下面的数更大，省去一列
      else
        i++;  //右上角小的话，这一行前面的数更小，下一行
    }
    return false;
  }
};

// @lc code=end
